package leetcode.code0441;

/**
 *
 * 执行用时：28 ms, 在所有 Java 提交中击败了5.35%的用户
 *
 * 内存消耗：42.4 MB, 在所有 Java 提交中击败了5.35%的用户
 *
 * 通过测试用例：1335 / 1335
 *
 * @author CaoYu
 * @date 2021年10月10日
 * @description
 */
public class Solution1 extends Solution441 {

	@Override
	public int arrangeCoins(int n) {
		return (int) (Math.sqrt(1 + 8.0 * n) - 1) >> 1;
	}

	public int arrangeCoins1(int n) {
		long total = 0;
		int l = 1;
		int r = (int) Math.sqrt((long) n * 2) + 1;
		int row = 1;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			total = (long) (mid + 1) * mid >> 1;
			if (total == n) {
				return mid;
			} else if (total > n) {
				r = mid - 1;
			} else {
				row = mid;
				l = mid + 1;
			}
		}
		return row;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		int ans = so.arrangeCoins(1804289383);
		System.out.println(ans);
	}

}
